﻿/*
题目: 最多可以参加的会议数目

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。

https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    /**
    * 有点像 会议室2（最大并发数）
    * 开始时间和结束时间 都会有影响
    * 所以需要排序 让开始时间可以同时考虑
    * 又需要使用 最小堆 来优先选择可以参加的会议
    * 使用 天为单位来进行统计（**重点**）
    *
    * 以天为单位，同时入队多个相同开始时间的会议，是为了选择这里面最早结束的会议
    * 用堆来维护那些还没参加 的会议
    */
    int maxEvents(vector<vector<int>>& events) {
        ::sort(events.begin(), events.end(), [](auto& x, auto& y) {
            return x[0] < y[0];
            });

        priority_queue<int, vector<int>, greater<int>> hp;

        int day = events[0][0];
        int i = 0;
        int res = 0;
        while (i < events.size() || !hp.empty()) {
            // 1. 入队所有同一时间开始的会议
            while (i < events.size() && events[i][0] == day) {
                hp.push(events[i++][1]);
            }

            // 2. 如果 day 太大了，那么太早的会议就无法参加了
            while (!hp.empty() && hp.top() < day) {
                hp.pop();
            }

            // 3. 今天来选择一个可以会议参加
            if (!hp.empty()) {
                hp.pop();
                res++;
            }

            day++;
        }

        return res;
    }
};
